#include <iostream>
#include <queue>
using namespace std;

class MGraph {
public:
    // 构造函数改进：可选初始化顶点数据
    MGraph(int n, int initVal = 0) : vertexNum(n) {
        // 动态分配内存
        vertex = new int[n];
        arc = new int*[n];
        visited = new int[n](); // 初始化为0
        
        // 初始化邻接矩阵和顶点数据
        for (int i = 0; i < n; ++i) {
            arc[i] = new int[n](); // 初始化为0
            vertex[i] = initVal;   // 初始化顶点数据
        }
    }

    ~MGraph() {
        // 释放内存（严格逆序）
        delete[] visited;
        for (int i = 0; i < vertexNum; ++i) {
            delete[] arc[i];
        }
        delete[] arc;
        delete[] vertex;
    }

    // 安全操作接口
    void addEdge(int v1, int v2) {
        if (isValidIndex(v1) && isValidIndex(v2)) {
            arc[v1][v2] = 1;
            arc[v2][v1] = 1; // 无向图
        }
    }

    void setVertex(int index, int value) {
        if (isValidIndex(index)) {
            vertex[index] = value;
        }
    }

    // 遍历接口
    void DFS() {
        resetVisited();
        for (int i = 0; i < vertexNum; ++i) {
            if (!visited[i]) {
                DFSTraverse(i);
            }
        }
        cout << endl;
    }

    void BFS() {
        resetVisited();
        queue<int> q;
        
        for (int i = 0; i < vertexNum; ++i) {
            if (!visited[i]) {
                visited[i] = 1;
                cout << vertex[i] << " ";
                q.push(i);
                
                while (!q.empty()) {
                    int v = q.front();
                    q.pop();
                    
                    for (int j = 0; j < vertexNum; ++j) {
                        if (arc[v][j] && !visited[j]) {
                            visited[j] = 1;
                            cout << vertex[j] << " ";
                            q.push(j);
                        }
                    }
                }
            }
        }
        cout << endl;
    }

private:
    // 辅助方法
    bool isValidIndex(int v) const {
        return v >= 0 && v < vertexNum;
    }

    void DFSTraverse(int v) {
        visited[v] = 1;
        cout << vertex[v] << " ";
        
        // 按顶点顺序访问（邻接矩阵特性）
        for (int i = 0; i < vertexNum; ++i) {
            if (arc[v][i] && !visited[i]) {
                DFSTraverse(i);
            }
        }
    }

    void resetVisited() {
        fill(visited, visited + vertexNum, 0);
    }

    // 数据成员
    int* vertex;    // 顶点数据数组
    int** arc;      // 邻接矩阵
    int* visited;   // 访问标记
    int vertexNum;  // 顶点总数
};

int main() {
    system("chcp 65001"); // 中文编码支持

    /* 构建以下结构的图：
        0
       / \
      1   2
     / \   \
    3   4   5
    */
    MGraph graph(6);
    for (int i = 0; i < 6; ++i) {
        graph.setVertex(i, i); // 正确设置顶点数据
    }

    // 添加边（自动处理无效索引）
    graph.addEdge(0, 1);
    graph.addEdge(0, 2);
    graph.addEdge(1, 3);
    graph.addEdge(1, 4);
    graph.addEdge(2, 5);
    graph.addEdge(-1, 10); // 测试无效输入

    cout << "邻接矩阵DFS遍历结果：\n";
    graph.DFS(); // 输出：0 1 3 4 2 5 

    cout << "邻接矩阵BFS遍历结果：\n";
    graph.BFS(); // 输出：0 1 2 3 4 5 

    return 0;
}